package jwebtest.queue;

/**
 * 队列双端链表实现： 长度不受限制并且插入和删除的时间复杂度都为O(1)
 * 
 * @author Yuanqy
 * 
 */
public class LinkQueue<T> {
	private class Node {
		private T obj;
		private Node next = null;

		Node(T obj) {
			this.obj = obj;
		}
	}

	private Node first = null;
	private Node last = null;
	private int size = 0;

	public void push(T obj) {
		Node Node = new Node(obj);
		if (first == null) {
			first = Node;
		} else {
			last.next = Node;
		}
		size++;
		last = Node;
	}

	public T peek() throws Exception {
		if (first == null)
			throw new Exception("empty");
		return first.obj;
	}

	public T pop() throws Exception {
		if (first == null)
			throw new Exception("empty");
		Node temp = first;
		if (first.next == null)
			last = null;
		first = first.next;
		size--;
		return temp.obj;
	}

	public boolean isEmpty() {
		return first == null;
	}

	public int size() {
		return size;
	}

	public void display() {
		if (first == null)
			System.out.println("empty");
		System.out.print("first -> last : | ");
		Node cur = first;
		while (cur != null) {
			System.out.print(cur.obj.toString() + " | ");
			cur = cur.next;
		}
		System.out.print("\n");
	}
}
